#include<bits/stdc++.h>
using namespace std;
const int MAXN=8e3+10,MAXM=2e4+10;
int n,m,head[MAXN*2],cnt,col[MAXN*2],recall[MAXN*4];
struct edge
{
	int v,next;
}e[MAXM*2];
void addedge(int x,int y)
{
	e[cnt]=(edge){y,head[x]};
	head[x]=cnt++;
	return;
}
bool dfs(int u)
{
	if(col[u]==1)return true;
	if(col[u]==2)return false;
	col[u]=1;
	col[u^1]=2;
	recall[++cnt]=u;
	recall[++cnt]=u^1;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(!dfs(v))return false;
	}
	return true;
}
bool solve()
{
	for(int i=0;i<n;++i)
	{
		if(col[i])continue;
		cnt=0;
		if(!dfs(i))
		{
			for(int j=1;j<=cnt;++j)col[recall[j]]=0;
			if(!dfs(i^1))return false;
		}
	}
	return true;
}
int main()
{
	while(scanf("%d%d",&n,&m)==2)
	{
		memset(head,-1,sizeof(head));
		memset(col,0,sizeof(col));
		cnt=0;
		n<<=1;
		for(int i=1;i<=m;++i)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			--x;--y;
			addedge(x,y^1);
			addedge(y,x^1);
		}
		if(solve())
			for(int i=0;i<n;++i)
			{
				if(col[i]==1)printf("%d\n",i+1);
			}
		else printf("NIE\n");
	}
	return 0;
}
